Redundant connection

Time: O(NLogN); Space: O(N); medium

In this problem, a tree is an undirected graph that is connected and has no cycles.

The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, …, N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.

Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.

Example 1:

The given undirected graph will be like this:

  1
 / \
2 - 3

Input: edges = [[1,2], [1,3], [2,3]]

Output: [2,3]

Example 2:

The given undirected graph will be like this:

5 - 1 - 2
    |   |
    4 - 3

Input: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]

Output: [1,4]

Constraints:

  • The size of the input 2D-array will be between 3 and 1000.

  • Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

[7]:

class UnionFind(object):
    def __init__(self, n):
        self.set = [x for x in range(n)]
        self.count = n

    def find_set(self, x):
        if self.set[x] != x:
            self.set[x] = self.find_set(self.set[x])  # path compression.
        return self.set[x]

    def union_set(self, x, y):
        x_root, y_root = list(map(self.find_set, (x, y)))

        if x_root == y_root:
            return False

        self.set[min(x_root, y_root)] = max(x_root, y_root)
        self.count -= 1

        return True

[8]:

class Solution1(object):
    def findRedundantConnection(self, edges) -> list:
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        uf = UnionFind(len(edges)+1)
        for edge in edges:
            if not uf.union_set(*edge):
                return edge
        return []

[9]:

s = Solution1()

edges = [[1,2], [1,3], [2,3]]
assert s.findRedundantConnection(edges) == [2,3]

edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
assert s.findRedundantConnection(edges) == [1,4]